import pandas as pd
data = pd.read_csv('dis.csv')
src = list(data['src'])
dst = list(data['dst'])

dic_neighbour = {}
lis = list(data['src'])
for i in range(len(lis)):
    if lis[i] not in dic_neighbour:
        dic_neighbour[lis[i]] = [data['dst'][i]]
    else:
        dic_neighbour[lis[i]].append(data['dst'][i])

lis = list(data['dst'])
for i in range(len(lis)):
    if lis[i] not in dic_neighbour:
        dic_neighbour[lis[i]] = [data['src'][i]]
    else:
        dic_neighbour[lis[i]].append(data['src'][i])

dic={}
for i in range(len(src)):
    if src[i] not in dic:
        dic[src[i]]=len(dic)
for i in range(len(dst)):
    if dst[i] not in dic:
        dic[dst[i]]=len(dic)

import numpy as np
distance = np.zeros((188,188))
for i in range(data.shape[0]):
    distance[dic[data['src'][i]],dic[data['dst'][i]]] = distance[dic[data['dst'][i]],dic[data['src'][i]]] = data['distance'][i]

class node:
    def __init__(self, city, neighbour, pre=None, current=float('inf')):
        self.city = city
        self.pre = pre
        self.current = current
        self.neighbour = neighbour
City=[]
for key, value in dic.items():
    Node = node(key,dic_neighbour[key])
    City.append(Node)

start = '北京'
end = '上海'
temp = start
find = [start]
feasible = []
while end not in find:
    for city in City[dic[temp]].neighbour:
        if city not in feasible and city not in find:
            feasible.append(city)
            City[dic[city]].current = City[dic[temp]].current+distance[dic[temp], dic[city]]
            City[dic[city]].pre = temp
        elif city in feasible and city not in find:
            dis = City[dic[temp]].current+distance[dic[temp], dic[city]]
            if dis < City[dic[city]].current:
                City[dic[city]].current = dis
                City[dic[city]].pre = temp
    min_ix = 0
    for i in range(len(feasible)):
        if City[dic[feasible[i]]].current < City[dic[feasible[min_ix]]].current:
            min_ix = i
    temp = feasible.pop(min_ix)
    find.append(temp)
print(find)
path = [end]
temp = end
while City[dic[temp]].pre != None:
    temp = City[dic[temp]].pre
    path.append(temp)
print(path)

